{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "google",
   "metadata": {},
   "source": [
    "##### Copyright 2025 Google LLC."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "apache",
   "metadata": {},
   "source": [
    "Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "you may not use this file except in compliance with the License.\n",
    "You may obtain a copy of the License at\n",
    "\n",
    "    http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software\n",
    "distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "See the License for the specific language governing permissions and\n",
    "limitations under the License.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "basename",
   "metadata": {},
   "source": [
    "# knapsack_2d_sat"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "link",
   "metadata": {},
   "source": [
    "<table align=\"left\">\n",
    "<td>\n",
    "<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/examples/knapsack_2d_sat.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
    "</td>\n",
    "<td>\n",
    "<a href=\"https://github.com/google/or-tools/blob/main/examples/python/knapsack_2d_sat.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
    "</td>\n",
    "</table>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "doc",
   "metadata": {},
   "source": [
    "First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "install",
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install ortools"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "description",
   "metadata": {},
   "source": [
    "\n",
    "Solver a 2D rectangle knapsack problem.\n",
    "\n",
    "This code is adapted from\n",
    "https://yetanothermathprogrammingconsultant.blogspot.com/2021/10/2d-knapsack-problem.html\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "code",
   "metadata": {},
   "outputs": [],
   "source": [
    "import io\n",
    "\n",
    "from ortools.sat.colab import flags\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "\n",
    "from google.protobuf import text_format\n",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "_OUTPUT_PROTO = flags.define_string(\n",
    "    \"output_proto\", \"\", \"Output file to write the cp_model proto to.\"\n",
    ")\n",
    "_PARAMS = flags.define_string(\n",
    "    \"params\",\n",
    "    \"num_search_workers:16,log_search_progress:true,max_time_in_seconds:45\",\n",
    "    \"Sat solver parameters.\",\n",
    ")\n",
    "_MODEL = flags.define_string(\n",
    "    \"model\", \"rotation\", \"'duplicate' or 'rotation' or 'optional'\"\n",
    ")\n",
    "\n",
    "\n",
    "def build_data() -> tuple[pd.Series, int, int]:\n",
    "    \"\"\"Build the data frame.\"\"\"\n",
    "    data = \"\"\"\n",
    "    item         width    height available    value    color\n",
    "    k1             20       4       2        338.984   blue\n",
    "    k2             12      17       6        849.246   orange\n",
    "    k3             20      12       2        524.022   green\n",
    "    k4             16       7       9        263.303   red\n",
    "    k5              3       6       3        113.436   purple\n",
    "    k6             13       5       3        551.072   brown\n",
    "    k7              4       7       6         86.166   pink\n",
    "    k8              6      18       8        755.094   grey\n",
    "    k9             14       2       7        223.516   olive\n",
    "    k10             9      11       5        369.560   cyan\n",
    "    \"\"\"\n",
    "\n",
    "    data = pd.read_table(io.StringIO(data), sep=r\"\\s+\")\n",
    "    print(\"Input data\")\n",
    "    print(data)\n",
    "\n",
    "    max_height = 20\n",
    "    max_width = 30\n",
    "\n",
    "    print(f\"Container max_width:{max_width} max_height:{max_height}\")\n",
    "    print(f\"#Items: {len(data.index)}\")\n",
    "    return (data, max_height, max_width)\n",
    "\n",
    "\n",
    "def solve_with_duplicate_items(\n",
    "    data: pd.Series, max_height: int, max_width: int\n",
    ") -> None:\n",
    "    \"\"\"solve the problem by building 2 items (rotated or not) for each item.\"\"\"\n",
    "    # Derived data (expanded to individual items).\n",
    "    data_widths = data[\"width\"].to_numpy()\n",
    "    data_heights = data[\"height\"].to_numpy()\n",
    "    data_availability = data[\"available\"].to_numpy()\n",
    "    data_values = data[\"value\"].to_numpy()\n",
    "\n",
    "    # Non duplicated items data.\n",
    "    base_item_widths = np.repeat(data_widths, data_availability)\n",
    "    base_item_heights = np.repeat(data_heights, data_availability)\n",
    "    base_item_values = np.repeat(data_values, data_availability)\n",
    "    num_data_items = len(base_item_values)\n",
    "\n",
    "    # Create rotated items by duplicating.\n",
    "    item_widths = np.concatenate((base_item_widths, base_item_heights))\n",
    "    item_heights = np.concatenate((base_item_heights, base_item_widths))\n",
    "    item_values = np.concatenate((base_item_values, base_item_values))\n",
    "\n",
    "    num_items = len(item_values)\n",
    "\n",
    "    # OR-Tools model\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    # Variables\n",
    "    x_starts = []\n",
    "    x_ends = []\n",
    "    y_starts = []\n",
    "    y_ends = []\n",
    "    is_used = []\n",
    "    x_intervals = []\n",
    "    y_intervals = []\n",
    "\n",
    "    for i in range(num_items):\n",
    "        ## Is the item used?\n",
    "        is_used.append(model.new_bool_var(f\"is_used{i}\"))\n",
    "\n",
    "        ## Item coordinates.\n",
    "        x_starts.append(model.new_int_var(0, max_width, f\"x_start{i}\"))\n",
    "        x_ends.append(model.new_int_var(0, max_width, f\"x_end{i}\"))\n",
    "        y_starts.append(model.new_int_var(0, max_height, f\"y_start{i}\"))\n",
    "        y_ends.append(model.new_int_var(0, max_height, f\"y_end{i}\"))\n",
    "\n",
    "        ## Interval variables.\n",
    "        x_intervals.append(\n",
    "            model.new_interval_var(\n",
    "                x_starts[i],\n",
    "                item_widths[i] * is_used[i],\n",
    "                x_ends[i],\n",
    "                f\"x_interval{i}\",\n",
    "            )\n",
    "        )\n",
    "        y_intervals.append(\n",
    "            model.new_interval_var(\n",
    "                y_starts[i],\n",
    "                item_heights[i] * is_used[i],\n",
    "                y_ends[i],\n",
    "                f\"y_interval{i}\",\n",
    "            )\n",
    "        )\n",
    "\n",
    "        # Unused boxes are fixed at (0.0).\n",
    "        model.add(x_starts[i] == 0).only_enforce_if(~is_used[i])\n",
    "        model.add(y_starts[i] == 0).only_enforce_if(~is_used[i])\n",
    "\n",
    "    # Constraints.\n",
    "\n",
    "    ## Only one of non-rotated/rotated pair can be used.\n",
    "    for i in range(num_data_items):\n",
    "        model.add(is_used[i] + is_used[i + num_data_items] <= 1)\n",
    "\n",
    "    ## 2D no overlap.\n",
    "    model.add_no_overlap_2d(x_intervals, y_intervals)\n",
    "\n",
    "    ## Objective.\n",
    "    model.maximize(cp_model.LinearExpr.weighted_sum(is_used, item_values))\n",
    "\n",
    "    # Output proto to file.\n",
    "    if _OUTPUT_PROTO.value:\n",
    "        print(f\"Writing proto to {_OUTPUT_PROTO.value}\")\n",
    "        with open(_OUTPUT_PROTO.value, \"w\") as text_file:\n",
    "            text_file.write(str(model))\n",
    "\n",
    "    # Solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    if _PARAMS.value:\n",
    "        text_format.Parse(_PARAMS.value, solver.parameters)\n",
    "\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    # Report solution.\n",
    "    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n",
    "        used = {i for i in range(num_items) if solver.boolean_value(is_used[i])}\n",
    "        data = pd.DataFrame(\n",
    "            {\n",
    "                \"x_start\": [solver.value(x_starts[i]) for i in used],\n",
    "                \"y_start\": [solver.value(y_starts[i]) for i in used],\n",
    "                \"item_width\": [item_widths[i] for i in used],\n",
    "                \"item_height\": [item_heights[i] for i in used],\n",
    "                \"x_end\": [solver.value(x_ends[i]) for i in used],\n",
    "                \"y_end\": [solver.value(y_ends[i]) for i in used],\n",
    "                \"item_value\": [item_values[i] for i in used],\n",
    "            }\n",
    "        )\n",
    "        print(data)\n",
    "\n",
    "\n",
    "def solve_with_duplicate_optional_items(\n",
    "    data: pd.Series, max_height: int, max_width: int\n",
    "):\n",
    "    \"\"\"solve the problem by building 2 optional items (rotated or not) for each item.\"\"\"\n",
    "    # Derived data (expanded to individual items).\n",
    "    data_widths = data[\"width\"].to_numpy()\n",
    "    data_heights = data[\"height\"].to_numpy()\n",
    "    data_availability = data[\"available\"].to_numpy()\n",
    "    data_values = data[\"value\"].to_numpy()\n",
    "\n",
    "    # Non duplicated items data.\n",
    "    base_item_widths = np.repeat(data_widths, data_availability)\n",
    "    base_item_heights = np.repeat(data_heights, data_availability)\n",
    "    base_item_values = np.repeat(data_values, data_availability)\n",
    "    num_data_items = len(base_item_values)\n",
    "\n",
    "    # Create rotated items by duplicating.\n",
    "    item_widths = np.concatenate((base_item_widths, base_item_heights))\n",
    "    item_heights = np.concatenate((base_item_heights, base_item_widths))\n",
    "    item_values = np.concatenate((base_item_values, base_item_values))\n",
    "\n",
    "    num_items = len(item_values)\n",
    "\n",
    "    # OR-Tools model\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    # Variables\n",
    "    x_starts = []\n",
    "    y_starts = []\n",
    "    is_used = []\n",
    "    x_intervals = []\n",
    "    y_intervals = []\n",
    "\n",
    "    for i in range(num_items):\n",
    "        ## Is the item used?\n",
    "        is_used.append(model.new_bool_var(f\"is_used{i}\"))\n",
    "\n",
    "        ## Item coordinates.\n",
    "        x_starts.append(\n",
    "            model.new_int_var(0, max_width - int(item_widths[i]), f\"x_start{i}\")\n",
    "        )\n",
    "        y_starts.append(\n",
    "            model.new_int_var(0, max_height - int(item_heights[i]), f\"y_start{i}\")\n",
    "        )\n",
    "\n",
    "        ## Interval variables.\n",
    "        x_intervals.append(\n",
    "            model.new_optional_fixed_size_interval_var(\n",
    "                x_starts[i], item_widths[i], is_used[i], f\"x_interval{i}\"\n",
    "            )\n",
    "        )\n",
    "        y_intervals.append(\n",
    "            model.new_optional_fixed_size_interval_var(\n",
    "                y_starts[i], item_heights[i], is_used[i], f\"y_interval{i}\"\n",
    "            )\n",
    "        )\n",
    "        # Unused boxes are fixed at (0.0).\n",
    "        model.add(x_starts[i] == 0).only_enforce_if(~is_used[i])\n",
    "        model.add(y_starts[i] == 0).only_enforce_if(~is_used[i])\n",
    "\n",
    "    # Constraints.\n",
    "\n",
    "    ## Only one of non-rotated/rotated pair can be used.\n",
    "    for i in range(num_data_items):\n",
    "        model.add(is_used[i] + is_used[i + num_data_items] <= 1)\n",
    "\n",
    "    ## 2D no overlap.\n",
    "    model.add_no_overlap_2d(x_intervals, y_intervals)\n",
    "\n",
    "    ## Objective.\n",
    "    model.maximize(cp_model.LinearExpr.weighted_sum(is_used, item_values))\n",
    "\n",
    "    # Output proto to file.\n",
    "    if _OUTPUT_PROTO.value:\n",
    "        print(f\"Writing proto to {_OUTPUT_PROTO.value}\")\n",
    "        with open(_OUTPUT_PROTO.value, \"w\") as text_file:\n",
    "            text_file.write(str(model))\n",
    "\n",
    "    # solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    if _PARAMS.value:\n",
    "        text_format.Parse(_PARAMS.value, solver.parameters)\n",
    "\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    # Report solution.\n",
    "    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n",
    "        used = {i for i in range(num_items) if solver.boolean_value(is_used[i])}\n",
    "        data = pd.DataFrame(\n",
    "            {\n",
    "                \"x_start\": [solver.value(x_starts[i]) for i in used],\n",
    "                \"y_start\": [solver.value(y_starts[i]) for i in used],\n",
    "                \"item_width\": [item_widths[i] for i in used],\n",
    "                \"item_height\": [item_heights[i] for i in used],\n",
    "                \"x_end\": [solver.value(x_starts[i]) + item_widths[i] for i in used],\n",
    "                \"y_end\": [solver.value(y_starts[i]) + item_heights[i] for i in used],\n",
    "                \"item_value\": [item_values[i] for i in used],\n",
    "            }\n",
    "        )\n",
    "        print(data)\n",
    "\n",
    "\n",
    "def solve_with_rotations(data: pd.Series, max_height: int, max_width: int):\n",
    "    \"\"\"solve the problem by rotating items.\"\"\"\n",
    "    # Derived data (expanded to individual items).\n",
    "    data_widths = data[\"width\"].to_numpy()\n",
    "    data_heights = data[\"height\"].to_numpy()\n",
    "    data_availability = data[\"available\"].to_numpy()\n",
    "    data_values = data[\"value\"].to_numpy()\n",
    "\n",
    "    item_widths = np.repeat(data_widths, data_availability)\n",
    "    item_heights = np.repeat(data_heights, data_availability)\n",
    "    item_values = np.repeat(data_values, data_availability)\n",
    "\n",
    "    num_items = len(item_widths)\n",
    "\n",
    "    # OR-Tools model.\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    # Coordinate variables for each rectangle.\n",
    "    x_starts = []\n",
    "    x_sizes = []\n",
    "    x_ends = []\n",
    "    y_starts = []\n",
    "    y_sizes = []\n",
    "    y_ends = []\n",
    "    x_intervals = []\n",
    "    y_intervals = []\n",
    "\n",
    "    for i in range(num_items):\n",
    "        sizes = [0, int(item_widths[i]), int(item_heights[i])]\n",
    "        # X coordinates.\n",
    "        x_starts.append(model.new_int_var(0, max_width, f\"x_start{i}\"))\n",
    "        x_sizes.append(\n",
    "            model.new_int_var_from_domain(\n",
    "                cp_model.Domain.FromValues(sizes), f\"x_size{i}\"\n",
    "            )\n",
    "        )\n",
    "        x_ends.append(model.new_int_var(0, max_width, f\"x_end{i}\"))\n",
    "\n",
    "        # Y coordinates.\n",
    "        y_starts.append(model.new_int_var(0, max_height, f\"y_start{i}\"))\n",
    "        y_sizes.append(\n",
    "            model.new_int_var_from_domain(\n",
    "                cp_model.Domain.FromValues(sizes), f\"y_size{i}\"\n",
    "            )\n",
    "        )\n",
    "        y_ends.append(model.new_int_var(0, max_height, f\"y_end{i}\"))\n",
    "\n",
    "        ## Interval variables\n",
    "        x_intervals.append(\n",
    "            model.new_interval_var(x_starts[i], x_sizes[i], x_ends[i], f\"x_interval{i}\")\n",
    "        )\n",
    "        y_intervals.append(\n",
    "            model.new_interval_var(y_starts[i], y_sizes[i], y_ends[i], f\"y_interval{i}\")\n",
    "        )\n",
    "\n",
    "    # is_used[i] == True if and only if item i is selected.\n",
    "    is_used = []\n",
    "\n",
    "    # Constraints.\n",
    "\n",
    "    ## for each item, decide is unselected, no_rotation, rotated.\n",
    "    for i in range(num_items):\n",
    "        not_selected = model.new_bool_var(f\"not_selected_{i}\")\n",
    "        no_rotation = model.new_bool_var(f\"no_rotation_{i}\")\n",
    "        rotated = model.new_bool_var(f\"rotated_{i}\")\n",
    "\n",
    "        ### Exactly one state must be chosen.\n",
    "        model.add_exactly_one(not_selected, no_rotation, rotated)\n",
    "\n",
    "        ### Define height and width according to the state.\n",
    "        dim1 = item_widths[i]\n",
    "        dim2 = item_heights[i]\n",
    "        # Unused boxes are fixed at (0.0).\n",
    "        model.add(x_sizes[i] == 0).only_enforce_if(not_selected)\n",
    "        model.add(y_sizes[i] == 0).only_enforce_if(not_selected)\n",
    "        model.add(x_starts[i] == 0).only_enforce_if(not_selected)\n",
    "        model.add(y_starts[i] == 0).only_enforce_if(not_selected)\n",
    "        # Sizes are fixed by the rotation.\n",
    "        model.add(x_sizes[i] == dim1).only_enforce_if(no_rotation)\n",
    "        model.add(y_sizes[i] == dim2).only_enforce_if(no_rotation)\n",
    "        model.add(x_sizes[i] == dim2).only_enforce_if(rotated)\n",
    "        model.add(y_sizes[i] == dim1).only_enforce_if(rotated)\n",
    "\n",
    "        is_used.append(~not_selected)\n",
    "\n",
    "    ## 2D no overlap.\n",
    "    model.add_no_overlap_2d(x_intervals, y_intervals)\n",
    "\n",
    "    # Objective.\n",
    "    model.maximize(cp_model.LinearExpr.weighted_sum(is_used, item_values))\n",
    "\n",
    "    # Output proto to file.\n",
    "    if _OUTPUT_PROTO.value:\n",
    "        print(f\"Writing proto to {_OUTPUT_PROTO.value}\")\n",
    "        with open(_OUTPUT_PROTO.value, \"w\") as text_file:\n",
    "            text_file.write(str(model))\n",
    "\n",
    "    # solve model.\n",
    "    solver = cp_model.CpSolver()\n",
    "    if _PARAMS.value:\n",
    "        text_format.Parse(_PARAMS.value, solver.parameters)\n",
    "\n",
    "    status = solver.solve(model)\n",
    "\n",
    "    # Report solution.\n",
    "    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):\n",
    "        used = {i for i in range(num_items) if solver.boolean_value(is_used[i])}\n",
    "        data = pd.DataFrame(\n",
    "            {\n",
    "                \"x_start\": [solver.value(x_starts[i]) for i in used],\n",
    "                \"y_start\": [solver.value(y_starts[i]) for i in used],\n",
    "                \"item_width\": [solver.value(x_sizes[i]) for i in used],\n",
    "                \"item_height\": [solver.value(y_sizes[i]) for i in used],\n",
    "                \"x_end\": [solver.value(x_ends[i]) for i in used],\n",
    "                \"y_end\": [solver.value(y_ends[i]) for i in used],\n",
    "                \"item_value\": [item_values[i] for i in used],\n",
    "            }\n",
    "        )\n",
    "        print(data)\n",
    "\n",
    "\n",
    "def main(_):\n",
    "    \"\"\"solve the problem with all models.\"\"\"\n",
    "    data, max_height, max_width = build_data()\n",
    "    if _MODEL.value == \"duplicate\":\n",
    "        solve_with_duplicate_items(data, max_height, max_width)\n",
    "    elif _MODEL.value == \"optional\":\n",
    "        solve_with_duplicate_optional_items(data, max_height, max_width)\n",
    "    else:\n",
    "        solve_with_rotations(data, max_height, max_width)\n",
    "\n",
    "\n",
    "main()\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "name": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
